Communications in Combinatorics and Optimization
Volume:7 Issue: 2, Summer-Autumn 2022

Let L(R) denote the set of all non-trivial left ideals of a ring R. The intersection graph of ideals of a ring R is an undirected simple graph denoted by G(R) whose vertices are in a one-to-one correspondence with L(R) and two distinct vertices are joined by an edge if and only if the corresponding left ideals of R have a non-zero intersection. The ideal structure of a ring reflects many ring theoretical properties. Thus much research has been conducted last few years to explore the properties of G(R). This is a survey of the developments in the study on the intersection graphs of ideals of rings since its introduction in 2009.

For a graph $G$, a set $L$ of vertices is called a total liar's domination if $|N_G(u)cap L|geq 2$ for any $uin V(G)$ and $|(N_G(u)cup N_G(v))cap L|geq 3$ for any distinct vertices $u,vin V(G)$. The total liar’s domination number is the cardinality of a minimum total liar’sdominating set of $G$ and is denoted by $gamma_{TLR}(G)$. In this paper we study the total liar's domination numbers of join and products of graphs.

The paired domination subdivision number of a graph $G$ is the minimum number of edges that must be subdivided (where each edge in $G$ can be subdivided at most once) in order to increase the paired domination number of $G$. In this note, we show that the problem of computing the paired-domination subdivision number is NP-hard for bipartite graphs.

For a simple, undirected, connected graph $G$, a function $h : V rightarrow lbrace 0, 1, 2 rbrace$ is called a total Roman ${2}$-dominating function (TR2DF) if for every vertex $v$ in $V$ with weight $0$, either there exists a vertex $u$ in $N_G(v)$ with weight $2$, or at least two vertices $x, y$ in $N_G(v)$ each with weight $1$, and the subgraph induced by the vertices with weight more than zero has no isolated vertices. The weight of TR2DF $h$ is $sum_{p in V} h(p)$. The problem of determining  TR2DF of minimum weight is called minimum total Roman {2}-domination problem (MTR2DP). We show that MTR2DP is polynomial time solvable for bounded treewidth graphs, threshold graphs and chain graphs. We design a $2 (ln(Delta - 0.5) + 1.5)$-approximation algorithm for the MTR2DP and show that the same cannot have $(1 - delta) ln |V|$ ratio approximation algorithm  for any $delta > 0$ unless $P = NP$.  Next, we show that MTR2DP is APX-hard for graphs with $ Delta=4$.  Finally, we show that the domination and TR2DF problems are not equivalent in computational complexity aspects.

The eccentric graph $G_e$ of a graph $G$ is a derived graph with the vertex set same as that of $G$ and two vertices in $G_e$ are adjacent if one of them is the eccentric vertex of the other. In this paper, the concepts of iterated eccentric graphs and eccentric completion of a graph are introduced and discussed.

Let $G=(E(G),V(G))$ be a (molecular) graph with vertex set $V(G)$ and edge set $E(G)$. The forgotten Zagreb index and the hyper Zagreb index of G are defined by $F(G) = sum_{u in V(G)} d(u)^{3}$ and $HM(G) = sum_{uv in E(G)}(d(u)+d(v))^{2}$ where $d(u)$ and d(v) are the degrees of the vertices $u$ and $v$ in $G$, respectively. A recent problem called the inverse problem deals with the numerical realizations of topological indices. We see that there exist trees for all even positive integers with $F(G)>88$ and with $HM(G)>158$. Along with the result, we show that there exist no trees with $F(G) < 90$ and $HM(G) < 160$ with some exceptional even positive integers and hence characterize the forgotten Zagreb index and the hyper Zagreb index for trees.

For a connected graph $G$ of order at least two, a  set $S$ of vertices in a graph $G$ is said to be an textit{outer connected monophonic set} if $S$ is a monophonic set of $G$ and either $S=V$ or the subgraph induced by $V-S$ is connected. The minimum cardinality of an outer connected monophonic set of $G$ is the textit{outer connected monophonic number} of $G$ and is denoted by $m_{oc}(G)$.  The number of extreme vertices in $G$ is its textit{extreme order} $ex(G)$.  A graph $G$ is said to be an textit{extreme outer connected monophonic graph} if $m_{oc}(G)$ = $ex(G)$.  Extreme outer connected monophonic graphs of order $p$ with outer connected monophonic number $p$ and extreme outer connected monophonic graphs of order $p$ with outer connected monophonic number $p-1$ are characterized.  It is shown that for every pair $a, b$ of integers with $0 leq a leq b$ and $b geq 2$, there exists a connected graph $G$ with $ex(G) = a$ and $m_{oc}(G) = b$. Also, it is shown that  for positive integers $r,d$ and $k geq 2$ with $r < d$, there exists an extreme outer connected monophonic graph $G$ with monophonic radius $r$, monophonic diameter $d$ and outer connected monophonic number $k$.

Topological indices are graph invariants computed usually by means of the distances or degrees of vertices of a graph. In chemical graph theory, a molecule can be modeled by a graph by replacing atoms by the vertices and bonds by the edges of this graph. Topological graph indices have been successfully used in determining the structural properties and in predicting certain physicochemical properties of chemical compounds. Wiener index is the oldest topological index which can be used for analyzing intrinsic properties of a molecular structure in chemistry. The Wiener index of a graph $G$ is equal to the sum of distances between all pairs of vertices of $G$. Recently, the entire versions of several indices have been introduced and studied due to their applications. Here we introduce the entire Wiener index of a graph. Exact values of this index for trees and some graph families are obtained, some properties and bounds for the entire Wiener index are established. Exact values of this new index for subdivision and $k$-subdivision graphs and some graph operations are obtained.

A dominating set $ D $ of a graph $ G=(V,E) $ is called a certified dominating set of $ G $ if $vert N(v) cap (V setminus D)vert$ is either 0 or at least 2 for all $ v in D$. The certified domination number $gamma_{cer}(G) $ is the minimum cardinality of a certified dominating set of $ G $. In this paper, we prove that the decision problem corresponding to $gamma_{cer}(G) $ is NP-complete for split graphs, star convex bipartite graphs, comb convex bipartite graphs and planar graphs. We also prove that it is linear time solvable for chain graphs, threshold graphs and bounded tree-width graphs.

For a graph $G$, an Italian dominating function is a function $f: V(G) rightarrow {0,1,2}$ such that for each vertex $v in V(G)$ either $f(v) neq 0$, or $sum_{u in N(v)} f(u) geq 2$. If a family $mathcal{F} = {f_1, f_2, dots, f_t}$ of distinct Italian dominating functions satisfy $sum^t_{i = 1} f_i(v) leq 2$ for each vertex $v$, then this is called an Italian dominating family. In [L. Volkmann, The {R}oman {${2}$}-domatic number of graphs, Discrete Appl. Math.  258 (2019), 235--241], Volkmann defined the Italian domatic number of $G$, $d_{I}(G)$, as the maximum cardinality of any Italian dominating family. In this same paper, questions were raised about the Italian domatic number of regular graphs. In this paper, we show that two of the conjectures are false, and examine some exceptions to a Nordhaus-Gaddum type inequality.

‎‎For an integer $kgeq 2$‎, ‎a Roman $k$-tuple dominating function‎, ‎(or just RkDF)‎, ‎in a graph $G$ is a function $f colon V(G) rightarrow {0‎, ‎1‎, ‎2}$ satisfying the condition that every vertex $u$ for which $f(u) = 0$ is adjacent to at least $k$ vertices $v$ for which $f(v) = 2$‎, ‎and every vertex $u$ for which $f(u) neq 0$ is adjacent to at least $k-1$ vertices $v$ for which $f(v) = 2$‎. ‎The Roman $k$-tuple domination number of ‎$‎G‎$‎‎ ‎is the minimum weight of an RkDF in $G$. ‎In this note we settle two problems posed in [Roman $k$-tuple Domination in Graphs‎, ‎Iranian J‎. ‎Math‎. ‎Sci‎. ‎Inform‎. ‎15 (2020)‎, ‎101--115]‎.

In this article the terminal status of a vertex and terminal status connectivity indices of a connected graph have introduced. Explicit formulae for the terminal status of vertices and for terminal status connectivity indices of certain graphs are obtained. Also some bounds are given for these indices. Further these indices are used for predicting the physico-chemical properties of cycloalkanes and it is observed that the correlation of physico-chemical properties of cycloalkanes with newly introduced indices is better than the correlation with other indices.

A   $k$-noncrossing tree is a noncrossing tree where each node receives a label in ${1,2,ldots,k}$ such that the sum of labels along an ascent does not exceed $k+1,$ if we consider a path from a fixed vertex called the root. In this paper, we provide a proof for a formula that counts the number of $k$-noncrossing trees in which the root (labelled by $k$) has degree $d$. We also find a formula for the number of forests in which each component is a $k$-noncrossing tree whose root is labelled by $k$.